(1) Field of the Invention
The invention relates to a system reliability evaluation method for routing policy, and especially relates to a system reliability evaluation method for routing policy of a stochastic-flow network.
(2) Description of the Prior Art
With diversification of commodities and information services, the factors of flow, time and cost are progressively valued in network analysis, but said factors are set as deterministic. Thus, in operations research, computer science, networking and other areas, the quickest path problem has attracted great attention of researchers, and said problem is for finding a quickest path with minimum transmission time to send a given amount of data from the unique source to the unique sink. Since then, several variants of quickest path problems are proposed: constrained quickest path problem, the first k quickest paths problem, and all-pairs quickest path problem.
However, two factors, flow and time, are separately dealt in conventional network analysis. For instance, the largest capacity path problem deals with flow, and the shortest path problem is for finding the shortest transmission time if time is regarded as parameter. Two factors, flow and time, are first combined in the quickest path problem, and the transmission time reduced is an important issue through the real-life network, especially through computer and telecommunication networks.
Due to the factors of failure, maintenance, occupation, etc, the capacity of each arc is stochastic in many real flow networks such as computer system, telecommunication system, logistic system and transportation system, etc. Because the capacity is influenced with said factors, the capacity should be not fixed. Such a network is named a stochastic-flow network. For example, in the computer system, each computer (or switch) represents a node, and each transmission line represents an arc. The transmission line is composed by plural real-life network lines (such as coaxial cables, fiber optics, etc), and each network line has two cases of normal and failure; that implies the transmission line has several states in which state k means k physical lines are successful. Thus each transmission line has plural states, and capacity of each arc has plural values accordingly
Thus, in computer and telecommunication networks, when the given amount of data is sent through several minimal paths, how to find the quickest transmission method in several various factors, calculate a system reliability denoted successful probability of transmitting the given amount of data in time restriction, and accord with the reserved paths for contribution to the system reliability. Namely, finding the best routing policy in time and cost restriction is an important issue to conduct the system reliability evaluation method for a stochastic-flow network.